#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0
#define ElemType int
#define MAXSIZE 100

typedef struct {
  ElemType elem[MAXSIZE];
  int last;
  /* int length; */
} SeqList;

/* void initial(SeqList *v) { */
/*   int i; */
/*   printf("请输入初始线性表长度: n="); */
/*   scanf("%d", &v->length); */
/*   printf("请输入1到%d的各元素\n", v->length); */
/*   getchar(); */
/*   for (i = 0; i < v->length; i++) { */
/*     scanf("%d", &v->elem[i]); */
/*     getchar(); */
/*   } */
/* } */

void initial(SeqList *v) {
  int i;
  printf("请输入初始线性表长度: n=");
  scanf("%d", &v->last);
  printf("请输入1到%d的各元素\n", v->last);
  getchar();
  for (i = 0; i < v->last; i++) {
    scanf("%d", &v->elem[i]);
    getchar();
  }
  v->last--;
}

/* int InsList(SeqList *L, int i, ElemType e) { */
/*   int k; */
/*   if (L->length >= MAXSIZE) { */
/*     printf("表已满,无法插入\n"); */
/*     return ERROR; */
/*   } */
/*   if ((i < 0) || (i > L->length)) { */
/*     printf("插入位置%d值不合法\n", i); */
/*     return ERROR; */
/*   } */
/*   for (k = L->length; k > i; k--) { */
/*     L->elem[k] = L->elem[k - 1]; */
/*   } */
/*   L->elem[i] = e; */
/*   L->length++; */
/*   return OK; */
/* } */
int InsList(SeqList *L, int i, ElemType e) {
  int k;
  if (L->last >= MAXSIZE - 1) {
    printf("表已满,无法插入\n");
    return ERROR;
  }
  if ((i < 1) || (i > L->last + 2)) {
    printf("插入位置%d值不合法\n", i);
    return ERROR;
  }
  for (k = L->last + 1; k > i - 1; k--) {
    L->elem[k] = L->elem[k - 1];
  }
  L->elem[i - 1] = e;
  L->last++;
  return OK;
}

/* int DelList(SeqList *L, int i, ElemType *e) { */
/*   int k; */
/*   if ((i < 0) || (i >= L->length)) { */
/*     printf("删除位置不合法\n"); */
/*     return ERROR; */
/*   } */
/*   *e = L->elem[i]; */
/*   for (k = i; k < L->length - 1; k++) { */
/*     L->elem[k] = L->elem[k + 1]; */
/*   } */
/*   L->length--; */
/*   return OK; */
/* } */
int DelList(SeqList *L, int i, ElemType *e) {
  int k;
  if ((i < 1) || (i >= L->last + 2)) {
    printf("删除位置不合法\n");
    return ERROR;
  }
  *e = L->elem[i - 1];
  for (k = i; k <= L->last; k++) {
    L->elem[k - 1] = L->elem[k];
  }
  L->last--;
  return OK;
}

/* int Locate(SeqList L, ElemType e) { */
/*   int i = 0; */
/*   while ((i < L.length) && (L.elem[i] != e)) { */
/*     i++; */
/*   } */
/*   if (i < L.length) { */
/*     return i; */
/*     /1* return i + 1; *1/ */
/*   } */
/*   return -1; */
/* } */
int Locate(SeqList L, ElemType e) {
  int i = 0;
  while ((i < L.last + 1) && (L.elem[i] != e)) {
    i++;
  }
  if (i < L.last + 1) {
    return i + 1;
    /* return i + 1; */
  }
  return -1;
}

/* void print(SeqList S) { */
/*   int i; */
/*   for (i = 0; i < S.length; i++) { */
/*     printf("%5d", S.elem[i]); */
/*   } */
/*   printf("\n"); */
/* } */
void print(SeqList S) {
  int i;
  for (i = 0; i <= S.last; i++) {
    printf("%5d", S.elem[i]);
  }
  printf("\n");
}

int main(void) {
  SeqList S;
  int loc, ch, temp;
  int flag = 1;
  char j;
  printf("本程序用来实现顺序结构的线性表.\n");
  printf("可以实现查找、插入、删除等操作.\n");
  initial(&S);
  while (flag) {
    printf("请选择:\n");
    printf("1.显示所有元素\n");
    printf("2.插入一个元素\n");
    printf("3.删除一个元素\n");
    printf("4.查找一个元素\n");
    printf("5.退出程序\n");
    scanf("%c", &j);
    getchar();
    switch (j) {
    case '1':
      print(S);
      break;
    case '2':
      printf("请输入要插入的元素和插入位置\n");
      printf("格式: 数据,位置; 例如:10,2\n");
      scanf("%d,%d", &ch, &loc);
      getchar();
      temp = InsList(&S, loc, ch);
      if (temp == ERROR) {
        printf("插入失败\n");
      } else {
        printf("插入成功\n");
      }
      print(S);
      break;
    case '3':
      printf("请输入要删除元素的位置\n");
      scanf("%d", &loc);
      getchar();
      temp = DelList(&S, loc, &ch);
      if (temp == ERROR) {
        printf("该元素不存在\n");
      } else {
        printf("删除了一个元素:%d\n", ch);
      }
      print(S);
      break;
    case '4':
      printf("请输入要查找的元素:");
      scanf("%d", &ch);
      getchar();
      loc = Locate(S, ch);
      if (loc != -1) {
        printf("该值是第%d个元素\n", loc);
      } else {
        printf("该元素不存在\n");
      }
      print(S);
      break;
    default:
      flag = 0;
      printf("程序结束,按任意键退出\n");
    }
  }
  return 0;
}

void merge(SeqList *LA, SeqList *LB, SeqList *LC) {
  int i, j, k;
  i = 0;
  j = 0;
  k = 0;
  while (i <= LA->last && j <= LB->last)
    if (LA->elem[i] <= LB->elem[j]) {
      LC->elem[k] = LA->elem[i];
      i++;
      k++;
    } else {
      LC->elem[k] = LB->elem[j];
      j++;
      k++;
    }
  while (i <= LA->last) /*当表LA有剩余元素时，则将表LA余下的元素赋给表LC*/
  {
    LC->elem[k] = LA->elem[i];
    i++;
    k++;
  }
  while (j <= LB->last) /*当表LB有剩余元素时，则将表LB余下的元素赋给表LC*/
  {
    LC->elem[k] = LB->elem[j];
    j++;
    k++;
  }
  LC->last = LA->last + LB->last + 1;
}
